Ordnung schaffen - Bäume
Binärer Suchbaum
Ein Baum weist mehrere Bestandteile auf:
Der Vorteil eines Baumes (in unserem Fall eines binären Suchbaumes) besteht darin, dass man die Werte, die man im Baum verwaltet, nicht sortieren muss, sondern man baut den Baum nach bestimmten Regeln auf und kann dann relativ schnell jeden Eintrag wieder finden. Ein solcher binärer Suchbaum wird nach folgendem Schema aufgebaut:
Der erste Wert kommt in die Wurzel. Der Wert des nächsten Listenelements wird mit dem in der Wurzel eingetragenen verglichen. Ist er kleiner, wird ein 'linkes Kind' erzeugt und der Wert dort abgelegt. Andernfalls erzeugen wir ein 'rechtes Kind', in dem wir unseren Wert ablegen. Ist der Knoten, in den man eintragen will schon belegt, vergleicht man ihn mit dem einzutragenden Wert auf die bereits beschriebene Weise und steigt somit den Baum solange herunter, bis der eigentliche Eintrag erfolgen kann. Auf diese Weise kann man den Baum auch jederzeit erweitern, ohne dass man etwas umsortieren müsste. Die Suche im Baum erfolgt einfach nach demselben Schema.
Wenn wir unsere Liste von oben durchschütteln ([22, 54, 5, 9, 82, 42, 3, 17, 79, 28, 76, 14, 61, 37, 43]) erhalten wir folgenden Baum:
Je nach Reihenfolge der Elemente in der Ausgangsliste kann der entstehende Baum dann auch anders aussehen. Auch hier gibt es viele unterschiedliche Bäume, die die Nachteile eines Binärbaums (z.B. die mögliche Unwucht in der Verteilung der Elemente) vermeiden, aber in ihren Regeln natürlich komplizierter sind.
Aufgaben
1) Überführe folgende Liste von Zahlen in einen binären Suchbaum: [27, 58, 16, 25, 4, 69, 84, 41, 63, 19]
2) Wie könnte man folgende Liste von Begriffen als binären Suchbaum darstellen? [Krokodil, Elefant, Nashorn, Maus, Marder, Fuchs, Dachs, Panther]
Verzeichnisbaum
Unter Windows werden Daten in einem Verzeichnisbaum gespeichert. Es können Ordner (Verzeichnis, Directory) angelegt werden. In jedem Ordner können weitere Ordner und Dateien abgelegt werden. Dabei ergibt sich eine Baumstruktur aus Ordnern (Stamm, Äste) und Dateien (Blätter):
- An der Wurzel des Baums steht der "Laufwerk-Buchstabe", z.B. "C:\"
- Für jedes Laufwerk, auch für externe Laufwerke, USB-Stick und CD-Laufwerk, wird ein separater Baum angelegt.
- Die Tiefe der Gliederung kann fast beliebig tief gemacht werden, d.h. Ordner im Ordner im Ordner, etc.
- Programme können ihre Daten an beliebige Stellen speichern und dort wieder ansprechen. Befehle "Speichern unter" und "Öffnen" benutzen und navigieren.
- Zur Navigation im Verzeichnisbaum verwendet man den Windows Explorer.
C:\Users\Bernd\Documents\Schule\2014-15\Info 6\binaercode.odg